UVa/10946 - You want what filled?/10946.cpp

   1 #include <iostream>
   2 #include <set>
   3 #include <algorithm>
   4
   5 using namespace std;
   6
   7 typedef pair<char, int> hole;
   8
   9 struct holeCompare{
  10   bool operator() (const hole &a, const hole &b) const{
  11     return (a.second < b.second) ||
  12       (a.second == b.second && a.first > b.first);
  13   }
  14 };
  15
  16 char g[50][50];
  17 bool visited[51][51];
  18 int r,c;
  19
  20 int di[] = {-1, 0, 1,  0};
  21 int dj[] = { 0, 1, 0, -1};
  22
  23 int dfs(const int &i,const int &j){
  24   int result = 1;
  25   visited[i][j] = true;
  26   for (int k = 0; k<4; ++k){
  27     int iNew, jNew;
  28     iNew = i + di[k];
  29     jNew = j + dj[k];
  30     if (0 <= iNew && iNew < r &&
  31         0 <= jNew && jNew < c &&
  32         !visited[iNew][jNew] &&
  33         g[i][j] == g[iNew][jNew]){
  34
  35       result += dfs(iNew, jNew);
  36     }
  37   }
  38   return result;
  39 }
  40
  41
  42 int main(){
  43   int problemNo = 1;
  44   while (cin >> r >> c && (r | c)){
  45     for (int i=0; i<r; ++i){
  46       for (int j=0; j<c; ++j){
  47         cin >> g[i][j];
  48         visited[i][j] = false;
  49       }
  50     }
  51
  52     multiset<hole, holeCompare> holes;
  53     for (int i=0; i<r; ++i){
  54       for (int j=0; j<c; ++j){
  55         if (!visited[i][j] && g[i][j] != '.'){
  56           holes.insert(hole(g[i][j], dfs(i,j)));
  57         }
  58       }
  59     }
  60     cout << "Problem " << problemNo++ << ":" << endl;
  61     for (multiset<hole>::reverse_iterator i = holes.rbegin(); i != holes.rend(); ++i){
  62       cout << i->first << " " << i->second << endl;
  63     }
  64   }
  65   return 0;
  66 }